翻訳と辞書
Words near each other
・ Long Geng Airport
・ Long Giang
・ Long Glacier
・ Long Glade Farm
・ Long Gone
・ Long Gone (album)
・ Long Gone (film)
・ Long Gone (instrumental)
・ Long Gone Before Daylight
・ Long Gone Daddy
・ Long Gone Day
・ Long Gone John
・ Long Gone Lonesome Blues
・ Long Goodbye (song)
・ Long Close School
Long code (mathematics)
・ Long Cold Winter
・ Long College for Women
・ Long Combination Vehicle
・ Long Common
・ Long Compton
・ Long Cool Woman in a Black Dress
・ Long Corridor
・ Long Count
・ Long County
・ Long County High School
・ Long County School District
・ Long County, Georgia
・ Long County, Shaanxi
・ Long Crag


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Long code (mathematics) : ウィキペディア英語版
Long code (mathematics)

In theoretical computer science and coding theory, the long code is an error-correcting code that is locally decodable. Long codes have an extremely poor rate, but play a fundamental role in the theory of hardness of approximation.
==Definition==
Let f_1,\dots,f_ : \^k\to \ for k=\log n be the list of ''all'' functions from \^k\to\.
Then the long code encoding of a message x\in\^k is the string f_1(x)\circ f_2(x)\circ\dots\circ f_(x) where \circ denotes concatenation of strings.
This string has length 2^n=2^.
The Walsh-Hadamard code is a subcode of the long code, and can be obtained by only using functions f_i that are linear functions when interpreted as functions \mathbb F_2^k\to\mathbb F_2 on the finite field with two elements. Since there are only 2^k such functions, the block length of the Walsh-Hadamard code is 2^k.
An equivalent definition of the long code is as follows:
The Long code encoding of j\in() is defined to be the truth table of the Boolean dictatorship function on the jth coordinate, i.e., the truth table of f:\^n\to\ with f(x_1,\dots,x_n)=x_i.〔Definition 7.3.1 in ( Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes) )〕
Thus, the Long code encodes a (\log n)-bit string as a 2^n-bit string.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Long code (mathematics)」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.